//给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 
//
// 
//
// 示例 1： 
//
// 
//输入:a = "11", b = "1"
//输出："100" 
//
// 示例 2： 
//
// 
//输入：a = "1010", b = "1011"
//输出："10101" 
//
// 
//
// 提示： 
//
// 
// 1 <= a.length, b.length <= 10⁴ 
// a 和 b 仅由字符 '0' 或 '1' 组成 
// 字符串如果不是 "0" ，就不含前导零 
// 
//
// Related Topics 位运算 数学 字符串 模拟 👍 1225 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution67 {
    public String addBinary(String a, String b) {

        int aLen = a.length(), bLen = b.length();
        char[] res ;
        if(aLen > bLen) {
            res = doAddBinary(aLen+1, a.toCharArray(), b.toCharArray());
        } else {
            res = doAddBinary(bLen+1, b.toCharArray(), a.toCharArray());
        }
        int cLen = res[res.length - 1] == '1' ? res.length : res.length - 1;
        char[] c = new char[cLen];
        for (int i = cLen - 1,j=0; i >=0; i--,j++) {
            c[j] = res[i];
        }
        return new String(c);
    }

    private char[] doAddBinary(int len, char[] longArr, char[] shortArr) {
        char[] res = new char[len];

        int longIdx = longArr.length - 1, shortIdx = shortArr.length - 1, resIdx = 0;
        while(longIdx >= 0 ) {
            char now;
            if(shortIdx >= 0) {
                boolean add = false;
                if(longArr[longIdx] == '0' && shortArr[shortIdx] == '0') {
                    now = '0';
                } else if(longArr[longIdx] == '1' && shortArr[shortIdx] == '1') {
                    now = '0';
                    add = true;
                } else {
                    now = '1';
                }

                if(add) {
                    res[resIdx+1] = '1';
                }
                char r = res[resIdx];
                if(r=='1') {
                    if(now == '1') {
                        res[resIdx] = '0';
                        res[resIdx+1] = '1';
                    }
                } else {
                    res[resIdx] = now;
                }
            } else {
                now = longArr[longIdx];
                char r = res[resIdx];
                if(r=='1') {
                    if(now == '1') {
                        res[resIdx] = '0';
                        res[resIdx+1] = '1';
                    }
                } else {
                    res[resIdx] = now;
                }
            }
            longIdx --;
            shortIdx --;
            resIdx++;
        }

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
